package BinaryTree;

import java.util.Arrays;
import java.util.HashMap;

/**
 * 前提：该二叉树没有重复节点，不然不能判断根节点的位置 -> 为什么要限制唯一，因为重复的值可能导致问题不可解
 * <p>
 * question: 根据二叉树的先序和中序数组，得到二叉树的后序遍历结果
 * <p>
 * examples:
 * int pre = {1,2,4,5,3,6,7}
 * int in = {4,2,5,1,6,3,7}
 * -> int pos = {4,5,2,6,7,3,1}
 *
 * @author Liaorun
 */
public class PreAndInArrayToPosArray {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(getPostArray(new int[]{1, 2, 4, 5, 3, 6, 7}, new int[]{4, 2, 5, 1, 6, 3, 7})));
    }

    public static int[] getPostArray(int[] pre, int[] in) {
        if (pre == null) {
            return null;
        }

        int n = pre.length;
        int[] pos = new int[n];

        // 记录中序遍历数组的位置，方便找每个子树的根节点
        HashMap<Integer, Integer> inMap = new HashMap<>(in.length);

        for (int i = 0; i < in.length; i++) {
            inMap.put(in[i], i);
        }

        set(pre, in, pos, 0, n - 1, 0, n - 1, 0, n - 1, inMap);

        return pos;
    }

    public static void set(int[] pre, int[] in, int[] pos, int prei, int prej, int ini, int inj, int posi, int posj, HashMap<Integer, Integer> inMap) {

        if (prei > prej) {
            return;
        }

        // base case 代表只有一个节点的二叉树
        if (prei == prej) {
            // 只剩下一个数了,代表只有一个节点的二叉树，直接填
            // 前序遍历的第一个 一定是 后序遍历的最后一个,也是根节点
            pos[posi] = pre[prei];
            return;
        }

        pos[posj] = pre[prei];

        // 找到整棵树的根节点在中序遍历的位置
        // 则左子树为[0,find - 1],右子树为[find + 1, in.length]
        int find = inMap.get(pre[prei]);

//        for (; find <= inj; find++) {
//            if (in[find] == pre[prei]) {
//                break;
//            }
//        }

        // 填当前节点的左子树部分
        set(pre, in, pos, prei + 1, prei + find - ini, ini, find - 1, posi, posi + find - ini - 1, inMap);
        // 填当前节点的右子树部分
        set(pre, in, pos, prei + find - ini + 1, prej, find + 1, inj, posi + find - ini, posj - 1, inMap);
    }
}
